Compare the running time of both algorithms for sorted, reverse-ordered, and random inputs. 6.13 Each deleteMin operation uses 2 logN comparisons in the worst case. a. Propose a scheme so that the deleteMin operation uses only logN + log logN + O(1) comparisons between elements. This need not imply less data movement. b. Extend your scheme in part ( a) so that only logN + log log logN + O(1) comparisons are performed. c. How far can you take this idea? d. Do the savings in comparisons compensate for the increased complexity of your algorithm? - | |
| View Solution | |
| << Back | Next >> |